

// 解法1： 递归
function postorder(root: Node | null): number[] {
    if(!root){
        return [];
    }
    const res = [];

    const postOrderTraversal = (node:  Node | null):void =>{
        if(!node){
            return
        }
        for(let item of node.children){
            postOrderTraversal(item)
        }
        res.push(node.val)
    }
    postOrderTraversal(root)
    return res;
};

// 解法2 利用前序遍历反转
// 例如：当前的节点为u，它的从左至右子节点依次为 v1,v2,v3 时
// 1.前序遍历结果：'[u,v1​,children(v1​),v2​,children(v2​),v3​,children(v3​)]'
// 2.后序遍历结果为：'[children(v1​),v1​,children(v2​),v2​,children(v3​),v3​,u]'
// 3.将前序遍历的顺序改为：根->右->左的遍历结果为：'[u,v3​,children(v3​),v2​,children(v2​),v1​,children(v1​)]'
// 将3的顺序倒序就得到了后序遍历的结果。
// 其中children(v1​)表示v1的为子树的遍历结果（不包括v1）
function postorder1(root: Node | null): number[] {
    if(!root){
        return [];
    }
    const res = [];
    let stack:Node[] = [];
    stack.push(root)
    while(stack.length){
        const node:Node = stack.pop();
        res.push(node.val);
        // 利用栈的特性，先把子节点依次从左往右放入栈中，然后再把栈的元素pop出来依次获取元素的数据。就实现了树的：根->右->左树的遍历方式。
        for(let item of node.children){
            stack.push(item)
        }
    }
    // 翻转遍历的结果
    res.reverse();
    return res;
};